package arrays;

import java.util.HashMap;
import java.util.Map;

/**
 * 题目：求数组中超过一半的数字
 *
 * @Author Gavin
 * @date 2021.12.23 22:05
 */
public class array_8 {
    /**
     * 第一种方法：借助一个hashmap来存储每个数字出现的次数，然后返回
     * 最大的次数的那个值就行，因为题目要求是超过一半的数字，出现次数最大
     * 的那个数就是超过一半的数字
     */
    //Time:O(n) Space:O(n)
    public static int solution_1(int[] array){
        Map<Integer,Integer> map=new HashMap<>();
        int max=0,count=0;
        for (int i = 0; i < array.length; i++) {
            //首先获取这个值对应的次数然后+1
            int preCount=map.getOrDefault(array[i],0)+1;
            map.put(array[i],preCount);
            if(preCount>count){
                max=i;
                count=preCount;
            }
        }
        return max;
    }
    /**
     * 第二种方法：采用摩尔投票法
     * 采用一个计数器，然后对出现的相同的数字进行加1，出现不同的数字就减1,
     * 这样最后留下的数字肯定就是超过一半的这个数字了
     * 比如： 1 2 1
     * 开始指向1，计数器+1后就为1
     * 然后指向2，此时不同，计数器-1
     * 然后指向1，此时计数器重新开始计算，又加1
     */
    //Time:O(n) Space:O(1)
    public static int solution_2(int[] array){
        int count=1,num=array[0];
        for (int i = 1; i < array.length; i++) {
            int pre=array[i];
            if(count==0){//关键点如果count为0就重新开始下一个计数了
                num=pre;
                count=1;
                continue;
            }
            if(num==pre)count++;
            else{
                count--;
            }
        }
        return num;
    }
}
